import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
//        System.out.println(new Solution().restoreIpAddresses("25525511135"));
        System.out.println(new Solution().restoreIpAddresses("0000"));
    }
}

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        backtracking(s, 0, new int[4], 0, ans);
        return ans;
    }

    void backtracking(String s, int start, int[] curIp, int curIdx, List<String> ans) {
        if (curIdx == 4) {  // add solution
            if (start < s.length()) {
                return;
            }
            StringBuilder ip = new StringBuilder();
            for (int j = 0; j < 4; j++) {
                ip.append(curIp[j]);
                if (j < 3) {
                    ip.append(".");
                }
            }
            ans.add(ip.toString());
            return;
        }

        //s的剩余位数太少或太多，剪枝
        if (s.length() - start < 4 - curIdx || s.length() - start > 3 * (4 - curIdx + 1)) {
            return;
        }

        if (s.charAt(start) == '0') {
            backtracking(s, start + 1, curIp, curIdx + 1, ans);
            return;
        }

        for (int i = 0; i < 3 && start + i < s.length(); i++) {
            curIp[curIdx] = curIp[curIdx] * 10 + s.charAt(start + i) - '0';
            if (curIp[curIdx] > 255) {
                break;
            }
            backtracking(s, start + i + 1, curIp, curIdx + 1, ans);
        }
        curIp[curIdx] = 0;
    }
}
